package chapter01;

import java.util.Comparator;
import java.util.PriorityQueue;

public class MergeKLists {
    //暴力
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode listNode=new ListNode(-1),p,q,head=listNode;
        if(lists.length<2){
            return lists.length==0?null:lists[0];
        }
        listNode.next=lists[0];
        for(int i=1;i<lists.length;i++){
            head=listNode;
            p=listNode.next;
            q=lists[i];
            while(p!=null&&q!=null){
                if(p.val<q.val){
                    listNode.next=p;
                    p=p.next;
                    listNode=listNode.next;
                }else{
                    listNode.next=q;
                    q=q.next;
                    listNode=listNode.next;
                }
            }
            listNode.next=p==null?q:p;
            listNode=head;
        }
        return listNode.next;
    }

    //优先级队列
    public ListNode mergeKLists1(ListNode[] lists) {
        ListNode listNode=new ListNode(-1);
        ListNode head=listNode;
        PriorityQueue<ListNode> priorityQueue=new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        for(ListNode listNode1:lists){
            if(listNode1!=null){
                priorityQueue.add(listNode1);
            }
        }
        while(!priorityQueue.isEmpty()){
            ListNode cur=priorityQueue.poll();
            head.next=cur;
            head=head.next;
            if(cur.next!=null){
                priorityQueue.add(cur.next);
            }
        }
        return listNode.next;
    }
    //二分
    public ListNode mergeKLists2(ListNode[] lists) {
        if(lists.length<2){
            return lists.length==0?null:lists[0];
        }
        return recursion(lists,0,lists.length-1);
    }

    public ListNode recursion(ListNode[] lists,int left,int right) {
        if(left==right){
            return lists[left];
        }
        int mid=(left+right)/2;
        ListNode leftList=recursion(lists, left,mid);
        ListNode rightList=recursion(lists,mid+1,right);
        return merge(leftList,rightList);
    }

    public ListNode merge(ListNode first,ListNode second){
        ListNode listNode=new ListNode(-1);
        ListNode head=listNode;
        while (first!=null&&second!=null){
            if(first.val<second.val){
                head.next=first;
                head=head.next;
                first=first.next;
            }else{
                head.next=second;
                head=head.next;
                second=second.next;
            }
        }
        head.next=first==null?second:first;
        return listNode.next;
    }


//    public static void main(String[] args) {
//        chapter01.ListNode listNode=new chapter01.ListNode(1);
//        chapter01.ListNode p1=listNode;
//        listNode.next=new chapter01.ListNode(4);
//        listNode=listNode.next;
//        listNode.next=new chapter01.ListNode(5);
//        listNode=listNode.next;
//
//        chapter01.ListNode listNode1=new chapter01.ListNode(1);
//        chapter01.ListNode p2=listNode1;
//        listNode1.next=new chapter01.ListNode(3);
//        listNode1=listNode1.next;
//        listNode1.next=new chapter01.ListNode(4);
//        listNode1=listNode1.next;
//
//        chapter01.ListNode listNode2=new chapter01.ListNode(2);
//        chapter01.ListNode p3=listNode2;
//        listNode2.next=new chapter01.ListNode(6);
//        listNode2=listNode2.next;
//
//        chapter01.ListNode list=new chapter01.MergeKLists().mergeKLists2(new chapter01.ListNode[]{p1,p2,p3});
//        while (list!=null){
//            System.out.print(list.val+" ");
//            list=list.next;
//        }
//    }
}
